A genetic algorithm is a heuristic method based on the mechanics of natural selection and genetics that is a powerful tool for finding solutions to optimization problems, i.e., finding optimal (or more optimal) feasible solutions to a problem under a set of objectives and constraints. A solution is “feasible” if it complies with all constraints binding the different variables, and infeasible if it does not comply with all constraints binding the different variables. An “optimal” solution is the most “fit” of the feasible solutions, where the fitness of a solution is determined by how it is scored by a fitness function. In other words, solution A is more fit—better—than solution B under a particular fitness function F if the fitness function F gives a higher score to solution A than to solution B.
A genetic algorithm typically includes generating a population of feasible solutions to a problem, ranking the solutions according to an objective fitness function, selecting some solutions to survive and/or reproduce, replacing or creating new solutions through genetic operators such as mutation (e.g., changing an existing solution or creating a new solution that has properties of other solutions), and iteratively repeating the steps of selection, ranking and creation/replacement until the algorithm terminates. Typically each generation of the algorithm will generate an improved solution, in the sense that the best solution that emerges after each generation is better than the best solution from the prior generation; and when the solutions begin to converge (i.e., when scores of the highest-ranking solutions cease to materially improve), there is a high degree of confidence (assuming a well-designed genetic algorithm) that the genetic algorithm has converged on a solution that is optimal or nearly so, and the algorithm terminates. Because they can efficiently search large, nonlinear and noisy solution spaces, genetic algorithms and associated genetic programming techniques are ideally-suited for solving optimization problems involving a large number of constraints and multiple different, sometimes inconsistent, objectives.
One example of such a problem is the creation of an Air Tasking Order in the context of a wartime air campaign. An Air Tasking Order (ATO) assigns aircraft and munitions to targets, and specifies the timing and grouping of air missions. It implements an air campaign that covers a 24 hour period. There is a planning cycle, the Master Air Attack Plan (MAAP) process, that precedes preparation of each ATO; once the ATO is issued the MAAP process begins again.
Often there are multiple different tactical objectives that must be satisfied by the ATO. For example, the planner may want to maximize a Probability of Destruction (PD) of a target while simultaneously minimizing attrition and mid-air refueling. The planner may also want to prioritize these objectives based on the mission at hand. Alternatively, a planner may consider minimizing attrition to be the top priority in one mission, while minimizing refueling may be of primary importance in another mission. The objectives may also change as the campaign progresses. Early in a campaign, for example, acquiring air supremacy and/or striking previously-known targets may be the highest tactical objectives, whereas later in the campaign the highest tactical objective may be destruction of pop-up targets and other time-sensitive targets (TSTs). Since an air campaign may involve hundreds of targets, dozens of aircraft units, and multiple possibly-competing tactical objectives, the ATO planning problem is a prime candidate for optimization using a genetic algorithm.